{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Duplicate File in System"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDuplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在系统中查找重复文件"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个目录信息列表&nbsp;<code>paths</code> ，包括目录路径，以及该目录中的所有文件及其内容，请你按路径返回文件系统中的所有重复文件。答案可按 <strong>任意顺序</strong> 返回。</p>\n",
    "\n",
    "<p>一组重复的文件至少包括 <strong>两个 </strong>具有完全相同内容的文件。</p>\n",
    "\n",
    "<p><strong>输入 </strong>列表中的单个目录信息字符串的格式如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)\"</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>这意味着，在目录&nbsp;<code>root/d1/d2/.../dm</code>&nbsp;下，有 <code>n</code> 个文件 ( <code>f1.txt</code>,&nbsp;<code>f2.txt</code>&nbsp;...&nbsp;<code>fn.txt</code> ) 的内容分别是 ( <code>f1_content</code>,&nbsp;<code>f2_content</code>&nbsp;...&nbsp;<code>fn_content</code> ) 。注意：<code>n &gt;= 1</code> 且 <code>m &gt;= 0</code> 。如果 <code>m = 0</code> ，则表示该目录是根目录。</p>\n",
    "\n",
    "<p><strong>输出 </strong>是由 <strong>重复文件路径组</strong> 构成的列表。其中每个组由所有具有相同内容文件的文件路径组成。文件路径是具有下列格式的字符串：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\"directory_path/file_name.txt\"</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [\"root/a 1.txt(abcd) 2.txt(efgh)\",\"root/c 3.txt(abcd)\",\"root/c/d 4.txt(efgh)\",\"root 4.txt(efgh)\"]\n",
    "<strong>输出：</strong>[[\"root/a/2.txt\",\"root/c/d/4.txt\",\"root/4.txt\"],[\"root/a/1.txt\",\"root/c/3.txt\"]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [\"root/a 1.txt(abcd) 2.txt(efgh)\",\"root/c 3.txt(abcd)\",\"root/c/d 4.txt(efgh)\"]\n",
    "<strong>输出：</strong>[[\"root/a/2.txt\",\"root/c/d/4.txt\"],[\"root/a/1.txt\",\"root/c/3.txt\"]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= paths.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= paths[i].length &lt;= 3000</code></li>\n",
    "\t<li><code>1 &lt;= sum(paths[i].length) &lt;= 5 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>paths[i]</code> 由英文字母、数字、字符 <code>'/'</code>、<code>'.'</code>、<code>'('</code>、<code>')'</code> 和 <code>' '</code> 组成</li>\n",
    "\t<li>你可以假设在同一目录中没有任何文件或目录共享相同的名称。</li>\n",
    "\t<li>你可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用单个空格分隔。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>假设您有一个真正的文件系统，您将如何搜索文件？广度搜索还是宽度搜索？</li>\n",
    "\t<li>如果文件内容非常大（GB级别），您将如何修改您的解决方案？</li>\n",
    "\t<li>如果每次只能读取 1 kb 的文件，您将如何修改解决方案？</li>\n",
    "\t<li>修改后的解决方案的时间复杂度是多少？其中最耗时的部分和消耗内存的部分是什么？如何优化？</li>\n",
    "\t<li>如何确保您发现的重复文件不是误报？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-duplicate-file-in-system](https://leetcode.cn/problems/find-duplicate-file-in-system/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-duplicate-file-in-system](https://leetcode.cn/problems/find-duplicate-file-in-system/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"root/a 1.txt(abcd) 2.txt(efgh)\",\"root/c 3.txt(abcd)\",\"root/c/d 4.txt(efgh)\",\"root 4.txt(efgh)\"]', '[\"root/a 1.txt(abcd) 2.txt(efgh)\",\"root/c 3.txt(abcd)\",\"root/c/d 4.txt(efgh)\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp = {}\n",
    "        for path in paths:\n",
    "            s = path.split(' ')\n",
    "            root = s[0]\n",
    "            for file in s[1:]:\n",
    "                name, content = file.split('(')\n",
    "                if content not in mp:\n",
    "                    mp[content] = [root+'/'+name]\n",
    "                else:\n",
    "                    mp[content].append(root+'/'+name)\n",
    "        res = []\n",
    "        for key in mp:\n",
    "            if len(mp[key]) >= 2:\n",
    "                res.append(mp[key])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hashtag = {}  #定义一个字典\n",
    "        for p in paths:  #对目录进行遍历\n",
    "            s = []\n",
    "            s = p.split(' ')  #将字符串s按空格分开，其中s[0]表示目录，\n",
    "            #print(s)\n",
    "            for val in s[1:]:  #对文件进行遍历\n",
    "                t, key = val.split(\"(\")  #将文件名和内容分开，这里直接用\"(\"分开即可\n",
    "                if key not in hashtag:\n",
    "                    hashtag[key] = [s[0] + '/' + t]\n",
    "                else:\n",
    "                    hashtag[key].append(s[0] + '/' + t)  #将内容相同的文件及其对应的目录储存\n",
    "        res = []\n",
    "        for key in hashtag:\n",
    "            if len(hashtag[key]) >= 2:  #判断是否为重复文件\n",
    "                res.append(hashtag[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hash={}\n",
    "        n=len(paths)\n",
    "        for i in range(n):\n",
    "            s=paths[i].split(\" \")\n",
    "            for j in range(1,len(s)):\n",
    "                path,key=s[j].split(\"(\")\n",
    "                if key not in hash:\n",
    "                    hash[key]=[s[0]+\"/\"+path]\n",
    "                else:\n",
    "                    hash[key].append(s[0]+\"/\"+path)\n",
    "        res=[]\n",
    "        for key in hash:\n",
    "            if len(hash[key])>=2:\n",
    "                res.append(hash[key])\n",
    "        return res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hashtag = {}  #定义一个字典\n",
    "        for p in paths:  #对目录进行遍历\n",
    "            s = []\n",
    "            s = p.split(' ')  #将字符串s按空格分开，其中s[0]表示目录，\n",
    "            #print(s)\n",
    "            for val in s[1:]:  #对文件进行遍历\n",
    "                t, key = val.split(\"(\")  #将文件名和内容分开，这里直接用\"(\"分开即可\n",
    "                if key not in hashtag:\n",
    "                    hashtag[key] = [s[0] + '/' + t]\n",
    "                else:\n",
    "                    hashtag[key].append(s[0] + '/' + t)  #将内容相同的文件及其对应的目录储存\n",
    "        res = []\n",
    "        for key in hashtag:\n",
    "            if len(hashtag[key]) >= 2:  #判断是否为重复文件\n",
    "                res.append(hashtag[key])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hash={}\n",
    "        n=len(paths)\n",
    "        for i in range(n):\n",
    "            s=paths[i].split(\" \")\n",
    "            for j in range(1,len(s)):\n",
    "                path,key=s[j].split(\"(\")\n",
    "                if key not in hash:\n",
    "                    hash[key]=[s[0]+\"/\"+path]\n",
    "                else:\n",
    "                    hash[key].append(s[0]+\"/\"+path)\n",
    "        res=[]\n",
    "        for key in hash:\n",
    "            if len(hash[key])>=2:\n",
    "                res.append(hash[key])\n",
    "        return res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        aux = {}\n",
    "        for path in paths:\n",
    "            values = path.split(\" \")\n",
    "            for i in range(1,len(values)):\n",
    "                num = values[i].split('(')\n",
    "                num[1] = num[1].replace(')','')\n",
    "                l = values[0] + '/' + num[0]\n",
    "                if num[1] in aux:\n",
    "                    aux[num[1]].append(l)\n",
    "                else:\n",
    "                    aux[num[1]] = [l]\n",
    "        ret = []\n",
    "        for key in aux.keys():\n",
    "            if len(aux[key]) > 1:\n",
    "                ret.append(aux[key])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        duplicate = {}\n",
    "        for line in paths:\n",
    "            adress = line.split(\" \")[0]\n",
    "            content = line.split(\" \")[1:]\n",
    "            for cnt in content:\n",
    "                cnt2 = cnt.split('(')[1]\n",
    "                cnt1 = cnt2.split(')')[0]\n",
    "                if cnt1 in duplicate:\n",
    "                    duplicate[cnt1].append(adress+'/'+cnt.split('(')[0])\n",
    "                else:\n",
    "                    duplicate[cnt1] = [adress+'/'+cnt.split('(')[0]]\n",
    "        res = []\n",
    "        for k,value in duplicate.items():\n",
    "            if len(value)>1:\n",
    "                res.append(value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for i in paths:\n",
    "            a = i.split(' ')\n",
    "            for j in a:\n",
    "                b = j.split('(')\n",
    "                if len(b) < 2:\n",
    "                    continue\n",
    "                if not b[1] in d:\n",
    "                    d[b[1]] = [a[0]+'/'+b[0]]\n",
    "                else:\n",
    "                    d[b[1]].append(a[0]+'/'+b[0])\n",
    "        c = []\n",
    "        for k,v in d.items():\n",
    "            if len(v) > 1:\n",
    "                c.append(v)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp = {}\n",
    "        for content in paths:\n",
    "            path, *files = content.split(' ')\n",
    "            for f in files:\n",
    "                fn, content = f.split('(')\n",
    "                content = content[:-1]\n",
    "                if content not in mp:\n",
    "                    mp[content] = []\n",
    "                mp[content].append(f'{path}/{fn}')\n",
    "        ret = []\n",
    "        for k, v in mp.items():\n",
    "            if len(v) > 1:\n",
    "                ret.append(v)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        def parse(strs):\n",
    "            strs_list = strs.split(' ')\n",
    "            path = strs_list[0]\n",
    "            name_contxt_list = strs_list[1:]\n",
    "            path_list = []\n",
    "            contxt_list = []\n",
    "            for name_contxt in name_contxt_list:\n",
    "                name,contxt = name_contxt.split('(')\n",
    "                file_path = path+'/'+name\n",
    "                path_list.append(file_path)\n",
    "                contxt_list.append(contxt)\n",
    "            return path_list,contxt_list\n",
    "        dicts = {}\n",
    "        for strs in paths:\n",
    "            file_path_list,contxt_list = parse(strs)\n",
    "            for i in range(len(file_path_list)):\n",
    "                file_path = file_path_list[i]\n",
    "                contxt = contxt_list[i]\n",
    "                if contxt in dicts.keys():\n",
    "                    dicts[contxt].append(file_path)\n",
    "                else:\n",
    "                    dicts[contxt] = [file_path]\n",
    "        ans = []\n",
    "        for key in dicts.keys():\n",
    "            if len(dicts[key])>1:\n",
    "                ans.append(dicts[key])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        aux = {}\n",
    "        for path in paths:\n",
    "            values = path.split(\" \")\n",
    "            for i in range(1,len(values)):\n",
    "                name_cont = values[i].split(\"(\")\n",
    "                name_cont[1] = name_cont[1].replace(\")\",\"\")\n",
    "                l = values[0] + \"/\" + name_cont[0]\n",
    "                if name_cont[1] in aux:\n",
    "                    aux[name_cont[1]].append(l)\n",
    "                else:\n",
    "                    aux[name_cont[1]] = [l]\n",
    "        res=[]\n",
    "        for key in aux.keys():\n",
    "            if len(aux[key]) > 1:\n",
    "                res.append(aux[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hashtag = defaultdict(list)\n",
    "        for p in paths:\n",
    "            s = p.split(' ')\n",
    "            for val in s[1:]:  #对文件进行遍历\n",
    "                t, key = val.split('(')\n",
    "                hashtag[key].append(s[0] + '/' + t)\n",
    "        \n",
    "        res = []\n",
    "        for key in hashtag:\n",
    "            if len(hashtag[key]) >= 2:  #判断是否为重复文件\n",
    "                res.append(hashtag[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        map = {}\n",
    "        for st in paths:\n",
    "            name = st.split()\n",
    "            root = name[0]\n",
    "            for i in range(1, len(name)):\n",
    "                name_list = name[i].split(\"(\")\n",
    "                content = name_list[1].replace(\")\", \"\")\n",
    "                map[content] = map.get(content, [])\n",
    "                map.get(content).append(root + \"/\" + name_list[0])\n",
    "        for item in map:\n",
    "            if len(map.get(item)) > 1:\n",
    "                res.append(map.get(item))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        fileDict = dict()\n",
    "        for path in paths:\n",
    "            pathArr = path.strip().split(\" \")\n",
    "            for i, file in enumerate(pathArr[1:]):\n",
    "                fileArr = file.split(\"(\")\n",
    "                content = fileArr[1][:-1]\n",
    "                fileDict.setdefault(content, []).append(pathArr[0] + \"/\" + fileArr[0])\n",
    "                # tmpList = fileDict.get(content, [])\n",
    "                # tmpList.append(pathArr[0] + \"/\" + fileArr[0])\n",
    "                # fileDict[content] = tmpList\n",
    "        res = []\n",
    "        for value in fileDict.values():\n",
    "            if len(value) > 1:\n",
    "                res.append(value)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\r\n",
    "class Solution:\r\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\r\n",
    "        content_map={}\r\n",
    "   \r\n",
    "        for path in paths:\r\n",
    "            dir,*files=path.split(' ')\r\n",
    "            for file in files:\r\n",
    "                for i in range(L:=len(file)-1,-1,-1):\r\n",
    "                    if file[i]=='(':\r\n",
    "                        content=file[i+1:L]\r\n",
    "                        sames=content_map.setdefault(content,[])\r\n",
    "                        sames.append(dir+'/'+file[:i])\r\n",
    "                        break\r\n",
    "        ret=[]\r\n",
    "        for v in content_map.values():\r\n",
    "            if len(v)>1:\r\n",
    "                ret.append(v)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        cp_map = {}\n",
    "        for i in range(len(paths)):\n",
    "            path_items = paths[i].split(' ')\n",
    "            dir = path_items[0]\n",
    "            for j in range(1, len(path_items)):\n",
    "                item = path_items[j]\n",
    "                c_start, c_end = item.find('('), item.find(')')\n",
    "                file_name = item[0: c_start]\n",
    "                file_content = item[c_start+1:c_end]\n",
    "                path = dir + '/' + file_name\n",
    "                values = cp_map.get(file_content, [])\n",
    "                values.append(path)\n",
    "                cp_map[file_content] = values\n",
    "        ret = []\n",
    "        for c, files in cp_map.items():\n",
    "            if len(files) >= 2:\n",
    "                ret.append(files)\n",
    "        return ret\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = []\n",
    "                \n",
    "                file_content_map[content].append(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = []\n",
    "                \n",
    "                file_content_map[content].append(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/find-duplicate-file-in-system/\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        m = {}\n",
    "        for path in paths:\n",
    "            if path == \"\":\n",
    "                continue\n",
    "            row = path.split(\" \")\n",
    "            if row.__len__() < 2:\n",
    "                continue\n",
    "            folder, files = row[0], row[1:]\n",
    "            for file in files:\n",
    "                tmp = file.split(\"(\")\n",
    "                if tmp.__len__() != 2:\n",
    "                    continue\n",
    "                filename = tmp[0]\n",
    "                content = tmp[1][:-1]\n",
    "                if content not in m.keys():\n",
    "                    m[content] = []\n",
    "                m[content].append(\"{}/{}\".format(folder, filename))\n",
    "        ans = []\n",
    "        for content, ps in m.items():\n",
    "            if ps.__len__() <= 1:\n",
    "                continue\n",
    "            ans.append(ps)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp=defaultdict(list)\n",
    "        for content in paths:\n",
    "            path, *files=content.split(' ')\n",
    "            for f in files:\n",
    "                fn, content = f.split('(')\n",
    "                content=content[:-1]\n",
    "                mp[content].append(f'{path}/{fn}')\n",
    "        ret = []\n",
    "        for k,v in mp.items():\n",
    "            if len(v)>1:\n",
    "                ret.append(v)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = []\n",
    "                \n",
    "                file_content_map[content].append(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        tmp = defaultdict(list)\n",
    "\n",
    "        for f in paths:\n",
    "            f = f.split(\" \")\n",
    "            for t in f[1:]:\n",
    "                t = t.split(\"(\")\n",
    "                tmp[t[1]].append(f[0] + \"/\" + t[0])\n",
    "\n",
    "        return [i for i in tmp.values() if len(i) > 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = collections.defaultdict(list)\n",
    "        for path in paths:\n",
    "            info = path.split()\n",
    "            for i in range(1, len(info)):\n",
    "                sub_info = info[i].strip(\")\").split(\"(\")\n",
    "                res[sub_info[1]].append(info[0] + \"/\" + sub_info[0])\n",
    "        return [l for _, l in res.items() if len(l) > 1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mulu = collections.defaultdict(list)\n",
    "        for path in paths:\n",
    "            wenjian  = path.split(\" \")\n",
    "            n = len(wenjian)\n",
    "            for i in range(1, n):\n",
    "                ind = wenjian[i].index(\"(\")\n",
    "                name = wenjian[i][:ind]\n",
    "                content = wenjian[i][ind+1:-1]\n",
    "                mulu[content].append(wenjian[0] + \"/\" + name)\n",
    "        ans = list()\n",
    "        for mu in mulu.keys():\n",
    "            if len(mulu[mu]) > 1:\n",
    "                ans.append(mulu[mu])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = defaultdict(list)\n",
    "        for path in paths:\n",
    "            f = path.split()\n",
    "            dir_path = f[0]\n",
    "            n = len(f)\n",
    "            for i in range(1,n):\n",
    "                F = f[i]\n",
    "                idx = F.find(\"(\")\n",
    "                file_name = F[:idx]\n",
    "                file_content = F[idx:]\n",
    "                file_path = dir_path + \"/\" + file_name\n",
    "                d[file_content].append(file_path)\n",
    "\n",
    "        ans = []\n",
    "        for k,v in d.items():\n",
    "            if len(v) > 1:\n",
    "                ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths):\n",
    "        import re\n",
    "        map = {}\n",
    "        ret = {}\n",
    "        res = []\n",
    "        for i in paths:\n",
    "\n",
    "            temp = i.split(\" \")\n",
    "            for j in temp[1:]:\n",
    "                match = re.search(r'(.*?)\\((.*?)\\)', j)\n",
    "                key = temp[0] + '/' + match.group(1)\n",
    "                value = match.group(2)\n",
    "                map[key] = value\n",
    "\n",
    "        for k, v in map.items():\n",
    "            if v not in ret:\n",
    "                ret[v] = [k]\n",
    "            else:\n",
    "                ret[v].append(k)\n",
    "        for i in ret.values():\n",
    "            if len(i)>=2:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        dic,re={},[]\n",
    "        lenre=0\n",
    "        for i in paths:\n",
    "            d=i.split(' ')\n",
    "            for j in d[1:]:\n",
    "                j=j.split('(')\n",
    "                if j[1] in dic:\n",
    "                    re[dic[j[1]]].append(d[0]+'/'+j[0])\n",
    "                else:\n",
    "                    dic[j[1]]=lenre\n",
    "                    re.append([d[0]+'/'+j[0]])\n",
    "                    lenre+=1\n",
    "        re=[i for i in re if len(i)>1]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "      paths_list = list()\n",
    "\n",
    "      txt_dir = dict()\n",
    "      for val in paths:\n",
    "          paths_list = val.split()\n",
    "          tem_dir = paths_list[0]\n",
    "          for j, path in enumerate(paths_list):\n",
    "              if j > 0:\n",
    "                  text_list = path.split(\"(\")\n",
    "                  root_path = tem_dir + \"/\" + text_list[0]\n",
    "                  txt_dir[root_path] = text_list[1].strip(\")\")\n",
    "      val_set = set(txt_dir.values())\n",
    "      res = []\n",
    "      if len(val_set) == len(txt_dir):\n",
    "          return res\n",
    "      for val_d in val_set:\n",
    "          val_list = []\n",
    "          for item_value in txt_dir:\n",
    "              if txt_dir[item_value] == val_d:\n",
    "                  val_list.append(item_value)\n",
    "          if len(val_list) > 1:\n",
    "              res.append(val_list)\n",
    "\n",
    "      return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        result = []\n",
    "        for i in paths:\n",
    "            if \" \" in i:\n",
    "                j = i.split()\n",
    "                j = [j[0] + \"/\" +k for k in j[1:]]\n",
    "                print(j)\n",
    "                result.extend(j)\n",
    "            else:\n",
    "                result.append(i)\n",
    "        all_result = {}\n",
    "        for i in result:\n",
    "            value, key = i.split(\"(\")\n",
    "            print(key, value)\n",
    "            if all_result.get(key):\n",
    "                all_result[key].append(value)\n",
    "            else:\n",
    "                all_result[key] = [value]\n",
    "\n",
    "        result = []\n",
    "        for key in all_result.keys():\n",
    "            if len(all_result[key]) > 1:\n",
    "                result.append(all_result[key])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import re\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        all_paths = []\n",
    "        for path in paths:\n",
    "            context_index = [s.start() for s in re.finditer('\\(', path)]\n",
    "            for i in range(len(context_index)):\n",
    "                all_paths.append(path.split()[0] + '/' + path.split()[1+i])\n",
    "\n",
    "        dic = {}\n",
    "        for path in all_paths:\n",
    "            context = path[path.index('(')+1:path.index(')')]\n",
    "\n",
    "            tmp = '/'.join(path[:path.index('(')].split())\n",
    "            if not dic.get(context):\n",
    "                dic[context] = [tmp]\n",
    "            else:\n",
    "                dic[context].append(tmp)\n",
    "\n",
    "        res = []\n",
    "        for key in dic.keys():\n",
    "            if len(dic[key]) > 1:\n",
    "                res.append(dic[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        count = {}\n",
    "        dic = {}\n",
    "        for line in paths:\n",
    "            p = line.split(\" \")\n",
    "            root = p[0]\n",
    "            files = p[1:]\n",
    "            for file in files:\n",
    "                d = file[:-1].split(\"(\")\n",
    "                file_name = d[0]\n",
    "                content = d[1]\n",
    "                if content in count:\n",
    "                    count[content] += 1\n",
    "                    dic[content].append(root+\"/\"+file_name)\n",
    "                else:\n",
    "                    count[content] = 1\n",
    "                    dic[content] = [root+\"/\"+file_name]\n",
    "        res = []\n",
    "        for content in count:\n",
    "            if count[content] >1:\n",
    "                res.append(dic[content])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for path in paths:\n",
    "            parts = path.split()\n",
    "            root = parts[0]\n",
    "            for i in range(1, len(parts)):\n",
    "                left_parenthesis = parts[i].index('(')\n",
    "                file_name = parts[i][:left_parenthesis]\n",
    "                content = parts[i][left_parenthesis + 1: -1]\n",
    "                if content in d.keys():\n",
    "                    d[content].append(root + '/' + file_name)\n",
    "                else:\n",
    "                    d[content] = [root + '/' + file_name]\n",
    "        ans = []\n",
    "        for k, v in d.items():\n",
    "            if len(v) > 1:\n",
    "                ans.append(v)\n",
    "        print(ans)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: [str]) -> [[str]]:\n",
    "        fileContent={}\n",
    "        for i in paths:\n",
    "            path=i.split()[0]\n",
    "            files=i.split()[1:]\n",
    "            \n",
    "            for f in files:\n",
    "                fname,content=f.split('(')\n",
    "                content=content[:-1]\n",
    "                if content in fileContent:\n",
    "                    fileContent[content].append(path+'/'+fname)\n",
    "                else:\n",
    "                    fileContent[content]=[path+'/'+fname]\n",
    "                \n",
    "        r=[]\n",
    "        for key,val in fileContent.items():\n",
    "            if len(val)>1:\n",
    "                r.append(val)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        con2path = {}\n",
    "        for file_content in paths:\n",
    "            file_list = file_content.split(\" \")\n",
    "            file_prefix = file_list[0]\n",
    "            for i in range(len(file_list) - 1):\n",
    "                [filename, filedata] = self.splitFileNameContent(file_list[i + 1])\n",
    "                if filedata in con2path:\n",
    "                    con2path[filedata].append(f\"{file_prefix}/{filename}\")\n",
    "                else:\n",
    "                    con2path[filedata] = [f\"{file_prefix}/{filename}\"]\n",
    "        result = []\n",
    "        for e in con2path:\n",
    "            if len(con2path[e]) > 1:\n",
    "                result.append(con2path[e])\n",
    "        return result\n",
    "\n",
    "    def splitFileNameContent(self, data: str) -> List[str]:\n",
    "        fi = data.find('(')\n",
    "        return [data[0:fi], data[fi + 1:-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        my_dic={}\n",
    "        for  x  in paths:\n",
    "            s=x.split(' ')\n",
    "            for data in s[1:]:\n",
    "                t,val=data.split('(')\n",
    "                if val not in my_dic:\n",
    "                    my_dic[val]=[s[0]+'/'+t]\n",
    "                else:\n",
    "                    my_dic[val].append(s[0]+'/'+t)\n",
    "        res=[]\n",
    "        for x in my_dic:\n",
    "            if len(my_dic[x])>=2:\n",
    "                res.append(my_dic[x])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for path in paths:\n",
    "            arr = path.split()\n",
    "            dir = arr[0]\n",
    "            for file in arr[1:]:\n",
    "                idx = file.index('(')\n",
    "                filename = file[0:idx]\n",
    "                content = file[idx + 1: -1]\n",
    "                absolutePath = dir + '/' + filename\n",
    "                if content not in d:\n",
    "                    d[content] = [absolutePath]\n",
    "                else:\n",
    "                    d[content].append(absolutePath)\n",
    "        return [x for x in d.values() if len(x) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp = collections.defaultdict(list)\n",
    "        dir = []\n",
    "        for p in paths:\n",
    "            files = p.split(\" \")\n",
    "            dir.append(files)\n",
    "\n",
    "        for d in dir:\n",
    "            for f in d[1:]:\n",
    "                name,cont = f.split(\"(\")\n",
    "                mp[cont].append(d[0]+\"/\"+name)\n",
    "        ans = []\n",
    "        for k in mp.keys():\n",
    "            if len(mp[k]) > 1:\n",
    "                ans.append(mp[k])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        n = len(paths)\n",
    "        file_dict = dict()\n",
    "        for i in range(n):\n",
    "            root_file = paths[i].split(' ')\n",
    "            for j in range(1,len(root_file)):\n",
    "                file_split_content = root_file[j].split('(')\n",
    "                file_content = file_split_content[-1]\n",
    "                if file_content in file_dict:\n",
    "                    file_dict[file_content].append(root_file[0]+'/'+file_split_content[0])\n",
    "                else:\n",
    "                    file_dict[file_content] = [root_file[0]+'/'+file_split_content[0]]\n",
    "\n",
    "        key_list = list(file_dict.keys())\n",
    "        for key in key_list:\n",
    "            if len(file_dict[key])==1:\n",
    "                file_dict.pop(key)\n",
    "        return list(file_dict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        hashmap = {}\n",
    "        res = []\n",
    "        for path in paths:\n",
    "            li = path.split(' ')\n",
    "            root = li[0]\n",
    "            for file in li[1:]:\n",
    "                content = file.split('(')[1]\n",
    "                if content in hashmap:\n",
    "                    hashmap[content].append(root + '/' + file.split('(')[0])\n",
    "                else:\n",
    "                    hashmap[content] = [root + '/' + file.split('(')[0]]\n",
    "        for i in hashmap.values():\n",
    "            if len(i) >= 2:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        dict = defaultdict(list)\n",
    "        ans = []\n",
    "\n",
    "        for phase in paths:\n",
    "            phase_split = phase.split(\" \")\n",
    "            for i in range(1, len(phase_split)):\n",
    "                small_split =phase_split[i].split(\"(\")\n",
    "                content = small_split[1][:-1]\n",
    "                dict[content].append(phase_split[0] +\"/\" + small_split[0])\n",
    "        print(dict)\n",
    "\n",
    "        for key in dict:\n",
    "            if len(dict[key]) > 1:\n",
    "                ans.append(dict[key])\n",
    "\n",
    "        return ans\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for path in paths:\n",
    "            words = path.split(' ')\n",
    "            dir_path = words[0]\n",
    "            for i in range(1, len(words)):\n",
    "                word = words[i]\n",
    "                pos = word.index('(')\n",
    "                file_name = word[:pos]\n",
    "                file_content = word[pos + 1: -1]\n",
    "                file_path = dir_path + '/' + file_name\n",
    "                if file_content in d:\n",
    "                    d[file_content].add(file_path)\n",
    "                else:\n",
    "                    d[file_content] = {file_path}\n",
    "        results = []\n",
    "        for result in d.values():\n",
    "            if len(result) >= 2:\n",
    "                results.append(list(result))\n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = dict()\n",
    "        res = []\n",
    "        for i in paths:\n",
    "            l = i.split(' ')\n",
    "            for j in l[1:]:\n",
    "                k = j.split('.')\n",
    "                if k[1] in d:\n",
    "                    d[k[1]].append(l[0]+'/'+k[0]+'.txt')\n",
    "                else:\n",
    "                    d[k[1]] = [l[0]+'/'+k[0]+'.txt']\n",
    "        for i in d:\n",
    "            if len(d[i])>1:\n",
    "                res.append(d[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        content = {}\n",
    "        for sub_path in paths:\n",
    "            root_path = sub_path.split()[0]\n",
    "            file_names = sub_path.split()[1:]\n",
    "            for tmp_name in file_names:\n",
    "                file_name = re.match(r'\\w+\\.txt', tmp_name).group()\n",
    "                file_content = re.search(r'\\((.*)\\)', tmp_name).group(1)\n",
    "                file_path = root_path + '/' + file_name\n",
    "                if  file_content not in content:\n",
    "                    content[file_content] = {file_path}\n",
    "                else:\n",
    "                    content[file_content].add(file_path)\n",
    "        res = []\n",
    "        for tmp in content.values():\n",
    "            if len(tmp) > 1:\n",
    "                res.append(list(tmp))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        context_map_path = {}\n",
    "        res = []\n",
    "        for path in paths:\n",
    "            words = path.split()\n",
    "            dir_path = words[0]\n",
    "            for file in words[1:]:\n",
    "                file_name,context = file[:-1].split('(')\n",
    "                if context not in context_map_path.keys():\n",
    "                    context_map_path[context] = []\n",
    "                context_map_path[context].append(dir_path+'/'+file_name)\n",
    "        for paths in context_map_path.values():\n",
    "            if len(paths) >=2 :\n",
    "                res.append(paths)\n",
    "        \n",
    "        return res\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        file_root = {}\n",
    "        content_file = defaultdict(list)\n",
    "\n",
    "        for path in paths :\n",
    "            ss = path.split(\" \")\n",
    "            root = ss[0]\n",
    "            for s in ss[1:] :\n",
    "                file,content = s.split(\"(\")\n",
    "                content_file[content].append(root + \"/\" + file)\n",
    "                file_root[file] = root\n",
    "        \n",
    "        return (list(v for v in content_file.values() if len(v) > 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        content_dict = collections.defaultdict(list)\n",
    "        for p in paths:\n",
    "            parts = p.split(' ')\n",
    "            path = parts[0]\n",
    "            for j in range(1, len(parts)):\n",
    "                name_content = parts[j].split('(')\n",
    "                file_name = name_content[0]\n",
    "                content = name_content[1][:-1]\n",
    "                content_dict[content].append(path+'/'+file_name)\n",
    "\n",
    "        return [i for i in content_dict.values() if len(i) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "from collections import defaultdict\n",
    "class File:\n",
    "    def __init__(self, file_name, file_type, file_content,file_path):\n",
    "        self.file_name = file_name\n",
    "        self.file_type = file_type\n",
    "        self.file_content = file_content\n",
    "        self.file_path = file_path\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        file_list = defaultdict(list)\n",
    "        res = []\n",
    "        for i in  paths:\n",
    "            j = i.split()\n",
    "            for x in j[1: len(j)]:\n",
    "                k = re.split('[()]', x)\n",
    "                if (k[0].split('.')[1], k[1]) not in file_list:\n",
    "                    file_list[(k[0].split('.')[1], k[1])] = [str(j[0]) + '/' + str(k[0])]\n",
    "                else:\n",
    "                    file_list[(k[0].split('.')[1], k[1])].append(str(j[0]) + '/' + str(k[0]))\n",
    "        for key in file_list:\n",
    "            if len(file_list[key]) > 1:\n",
    "                res.append(file_list[key])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "\n",
    "        ans = []\n",
    "        text_dict = dict()\n",
    "        for index , data in enumerate(paths):\n",
    "            data_list = data.strip().split()\n",
    "            path = data_list[0] + '/'\n",
    "\n",
    "            for file in range(1,len(data_list)):\n",
    "                file_split = data_list[file].split('(')\n",
    "                file_name = file_split[0]\n",
    "                file_text = file_split[1].split(')')[0]\n",
    "                if file_text not in text_dict:\n",
    "                    text_dict[file_text] = [path+file_name]\n",
    "                else:\n",
    "                    text_dict[file_text].append(path+file_name)\n",
    "        print(text_dict)\n",
    "        for _, value in text_dict.items():\n",
    "            if len(value) >1:\n",
    "                ans.append(value)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for p in paths:\n",
    "            lst = p.split(' ')\n",
    "            for i in range(1, len(lst)):\n",
    "                m = re.match(r'(.+)\\((.+)\\)', lst[i])\n",
    "                x = m.group(1)\n",
    "                y = m.group(2)\n",
    "                if y not in d.keys():\n",
    "                    d[y] = []\n",
    "                d[y].append(lst[0] + '/' + x)\n",
    "        ans = []\n",
    "        for k, v in d.items():\n",
    "            if len(v) > 1:\n",
    "                ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import re\n",
    "\n",
    "reg = \"(.*)\\((.*)\\)\"\n",
    "\n",
    "def parse(f):\n",
    "    m = re.match(reg, f).groups()\n",
    "    return m[0], m[1]\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        groups = collections.defaultdict(list)\n",
    "        for path in paths:\n",
    "            dir, *files = path.strip().split()\n",
    "            for f in files:\n",
    "                fname, content = parse(f)\n",
    "                groups[content].append(dir+\"/\"+fname)\n",
    "        return [fs for c, fs in groups.items() if len(fs) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        ret_dict = {} \n",
    "        for path in paths:\n",
    "            ps = path.split(\" \")\n",
    "            for p in ps[1:]:\n",
    "                tmps = p.split(\"(\")\n",
    "                name= tmps[0]\n",
    "                content = tmps[1].split(\")\")[0]\n",
    "\n",
    "                if content not in ret_dict:\n",
    "                    ret_dict[content] = [\"{}/{}\".format(ps[0], name)]\n",
    "                else:\n",
    "                    ret_dict[content].append(\"{}/{}\".format(ps[0], name))\n",
    "        print(ret_dict)\n",
    "        return [v for k, v in ret_dict.items() if len(v) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        from collections import defaultdict\n",
    "        \n",
    "        # 用文件内容的哈希值作为索引保存文件名; 若文件内容一致, 则它们的文件名会在一个键值对中\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        def getPathAndContent(s):\n",
    "            nonlocal d\n",
    "            if isinstance(s, list):\n",
    "                ans = []\n",
    "                for i in s:\n",
    "                    getPathAndContent(i)\n",
    "                return\n",
    "            \n",
    "            import re\n",
    "            ans = [p for p in re.split(r' |\\(|\\)', s) if len(p)]\n",
    "            path = ans.pop(0)\n",
    "            for i in range(len(ans)//2):\n",
    "                fullpath, content = path + '/' + ans[2*i], ans[2*i+1]\n",
    "                d[content].append(fullpath)\n",
    "            return\n",
    "        \n",
    "        # 记录哈希值-文件名\n",
    "        getPathAndContent(paths)\n",
    "\n",
    "        # 筛选重复文件\n",
    "        ans = []\n",
    "        for v in d.values():\n",
    "            if len(v) > 1:\n",
    "                ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parse_dir(self, directory):\n",
    "        stk = []\n",
    "        splits = directory.split('/')\n",
    "        for sp in splits:\n",
    "            if not sp:\n",
    "                continue\n",
    "            # consists only dot?\n",
    "            nodot = sp.replace('.', '')\n",
    "            if not nodot:\n",
    "                if sp == '.':\n",
    "                    continue\n",
    "                n = len(sp) - 1\n",
    "                for _ in range(n):\n",
    "                    if not stk:\n",
    "                        break\n",
    "                    stk.pop()\n",
    "            else:\n",
    "                stk.append(sp)\n",
    "        return '/'.join(stk)\n",
    "        \n",
    "    def parse_file(self, fileinfo):\n",
    "        bracidx = fileinfo.find('(')\n",
    "        filename = fileinfo[:bracidx]\n",
    "        content = fileinfo[bracidx + 1:len(fileinfo) - 1]\n",
    "        return filename, content\n",
    "\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        mp_content_filepaths = {}\n",
    "        for p in paths:\n",
    "            splits = p.split(' ')\n",
    "            directory = self.parse_dir(splits[0])\n",
    "            for i in range(1, len(splits)):\n",
    "                split = splits[i]\n",
    "                filename, content = self.parse_file(split)\n",
    "                filepath = '%s/%s' % (directory, filename)\n",
    "                if content not in mp_content_filepaths:\n",
    "                    mp_content_filepaths[content] = []\n",
    "                mp_content_filepaths[content].append(filepath)\n",
    "        ans = []\n",
    "        for v in mp_content_filepaths.values():\n",
    "            if len(v) >= 2:\n",
    "                ans.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "\n",
    "\n",
    "        dictL = defaultdict(list)\n",
    "\n",
    "        for path in paths:\n",
    "            ListT = path.split()\n",
    "            n = len(ListT)\n",
    "            for i in range(1,n):\n",
    "                str1 = ListT[i].split(\"(\")[0]\n",
    "                str2 = ListT[i].split(\"(\")[1][:-1]\n",
    "            \n",
    "                dictL[str2].append(ListT[0]+\"/\"+str1)\n",
    "        ans = []\n",
    "        for key ,val in dictL.items():\n",
    "            if len(val) > 1:\n",
    "                ans.append(list(val))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        content_dict = defaultdict(list)\n",
    "        for i in paths:\n",
    "            tmp = i.split()\n",
    "            path = tmp[0]\n",
    "            file_list = tmp[1:]\n",
    "            for file in file_list:\n",
    "                index = file.index('(')\n",
    "                name = file[:index]\n",
    "                content = file[index+1:-1]\n",
    "                content_dict[content].append((path, name))\n",
    "        res = []\n",
    "        for k, v in content_dict.items():\n",
    "            if len(v) > 1:\n",
    "                tmp = []\n",
    "                for i in v:\n",
    "                    tmp.append('/'.join(i))\n",
    "                res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        content_dict = defaultdict(list)\n",
    "        for i in paths:\n",
    "            tmp = i.split()\n",
    "            path = tmp[0]\n",
    "            file_list = tmp[1:]\n",
    "            for file in file_list:\n",
    "                index = file.index('(')\n",
    "                name = file[:index]\n",
    "                content = file[index+1:-1]\n",
    "                content_dict[content].append((path, name))\n",
    "        res = []\n",
    "        for k, v in content_dict.items():\n",
    "            if len(v) > 1:\n",
    "                tmp = []\n",
    "                for i in v:\n",
    "                    tmp.append('/'.join(i))\n",
    "                res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        file_dict = {}\n",
    "        for path in paths:\n",
    "            files = path.split(' ')\n",
    "            dir = files[0]\n",
    "            for file in files[1:]:\n",
    "                lidx = file.index('(')\n",
    "                ridx = file.rindex(')')\n",
    "                content = file[lidx + 1:ridx]\n",
    "                if file_dict.get(content) is None:\n",
    "                    file_dict[content] = []\n",
    "                    file_dict[content].append(dir + \"/\" + file[:lidx])\n",
    "                file_dict[content].append(dir + \"/\" + file[:lidx])\n",
    "        result = []\n",
    "        for value in file_dict.values():\n",
    "            if len(value) > 2:\n",
    "                result.append(value[1:])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        from collections import defaultdict\n",
    "        file_dict=defaultdict(list)\n",
    "        for path in paths:\n",
    "            lTemp=path.split(\" \")\n",
    "            #lTemp.reverse()\n",
    "            first=lTemp.pop(0)\n",
    "            print(lTemp)\n",
    "            for item in lTemp[0:len(lTemp)]:\n",
    "                idx=item.find(\"(\")\n",
    "                if idx!=-1:\n",
    "                    ke=item[idx:]\n",
    "                    file_dict[ke].append(first+\"/\"+item[0:idx])\n",
    "        print(file_dict)\n",
    "        res=[]\n",
    "        for v in file_dict.values():\n",
    "            if len(v)>1:\n",
    "                res.append(v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        dict = defaultdict(list)\n",
    "        for each in paths:\n",
    "            each_list = each.split(' ')\n",
    "            root = each_list[0]\n",
    "            files = each_list[1:]\n",
    "            for f in files:\n",
    "                file_content = f.split('(')\n",
    "                dict[file_content[1][:-1]].append([root, file_content[0]])\n",
    "        res = list()\n",
    "        for v in dict.values():\n",
    "            ans = ['/'.join(x) for x in v]\n",
    "            if len(ans) > 1:\n",
    "                res.append(ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        if not paths:\n",
    "            return\n",
    "        res = paths[0].split(' ')\n",
    "        res2 = []\n",
    "        res3 = []\n",
    "        for j in range(len(paths)):\n",
    "            res = paths[j].split(' ')\n",
    "            n = len(res)\n",
    "            for i in range(1, n):\n",
    "                res2.append(res[0] + '/' + res[i])\n",
    "        res4 = {}  \n",
    "        # res4: {'abcd': ['root/a/1.txt'], 'efsfgh': ['root/a/2.txt'], 'abdfcd': ['root/c/3.txt'], 'efggdfh': ['root/c/d/4.txt']}\n",
    "        for i, items in enumerate(res2):\n",
    "            res3 = items.split('(')\n",
    "            a = list()\n",
    "            a.append(res3[0])\n",
    "            if res3[1][:-1] in res4:\n",
    "                res4[res3[1][:-1]].append(res3[0])\n",
    "            else:\n",
    "                res4[res3[1][:-1]] = a\n",
    "        res5 = []\n",
    "        # 遍历字典的值\n",
    "        for value in res4.values():\n",
    "            if len(value) > 1:\n",
    "                res5.append(value)\n",
    "        return res5\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # res4[res3[1][:-1]] = a\n",
    "        # print('res4:', res4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        # k = paths[0]\n",
    "        # list1 = k.split()\n",
    "        # l1 = list1[0] + '/' + list1[1]\n",
    "        # l2 = list1[0] + '/' + list1[2]\n",
    "        # print(l1,l2)\n",
    "\n",
    "        list2 = []\n",
    "        for i in paths:\n",
    "            list1 = i.split()\n",
    "            for j, value in enumerate(list1[1::]):\n",
    "                list2.append(list1[0] + '/' + value)\n",
    "        dict1 = {}\n",
    "        for i in list2:\n",
    "            print(i)\n",
    "            for j,v in enumerate(i):\n",
    "                if v == '(':\n",
    "                    if not dict1.get(i[j::]):\n",
    "                        dict1[i[j::]] = [i[:j]]\n",
    "                    else:                  \n",
    "                        dict1[i[j::]].append(i[:j])\n",
    "        res = []\n",
    "        for i in dict1:\n",
    "            if len(dict1[i]) > 1:\n",
    "                res.append(dict1[i])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:################哈希，O(n)\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        ps = []; contents = []\n",
    "        for path in paths:\n",
    "            parts = path.split(\" \")\n",
    "            for part in parts[1:]:\n",
    "                ps.append(parts[0] + \"/\" + part.split(\"(\")[0]); contents.append(part.split(\"(\")[1])\n",
    "        ans = collections.defaultdict(list)\n",
    "        for i, p in enumerate(ps):\n",
    "            ans[contents[i]].append(p)\n",
    "        ans = [x for x in ans.values() if len(x) >= 2]\n",
    "        return ans\n",
    "\n",
    "class Solution2:################并查集，超时，O(n^2)\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        ps = []; contents = []\n",
    "        for path in paths:\n",
    "            parts = path.split(\" \")\n",
    "            for part in parts[1:]:\n",
    "                ps.append(parts[0] + \"/\" + part.split(\"(\")[0]); contents.append(part.split(\"(\")[1])\n",
    "        n = len(ps); uf = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if contents[i] == contents[j]:\n",
    "                    uf.Union(i, j)\n",
    "        # print(uf.parents)\n",
    "        ans = collections.defaultdict(list)\n",
    "        for i, p in enumerate(uf.parents):\n",
    "            ans[uf.parents[i]].append(ps[i])\n",
    "        ans = [x for x in ans.values() if len(x) >= 2]\n",
    "        return ans\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parents = list(range(n))\n",
    "\n",
    "    def Find(self, x):\n",
    "        if x == self.parents[x]:\n",
    "            return x\n",
    "        return self.Find(self.parents[x])\n",
    "\n",
    "    def Union(self, x, y):\n",
    "        rootx = self.Find(x)\n",
    "        rooty = self.Find(y)\n",
    "        self.parents[x] = y\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        num_dic, path_dic = {}, {}\n",
    "        res = []\n",
    "        for st in paths:\n",
    "            file = st.split(' ')[1:]\n",
    "            for f in file:\n",
    "                index = f.index('(')\n",
    "                if f[index + 1:-1] not in num_dic.keys():\n",
    "                    num_dic[f[index + 1: -1]] = 1\n",
    "                    path_dic[f[index + 1: -1]] = [st.split(' ')[0]+'/'+ f.split('(')[0]]\n",
    "                else:\n",
    "                    num_dic[f[index + 1: -1]] += 1\n",
    "                    path_dic[f[index + 1: -1]].append(st.split(' ')[0]+'/'+ f.split('(')[0])\n",
    "        output = []\n",
    "        for key, value in num_dic.items():\n",
    "            if value > 1:\n",
    "                output.append(path_dic[key])\n",
    "        # print(num_dic)\n",
    "        # print(path_dic)\n",
    "        return output     \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        tempd = {}\n",
    "        res = {}\n",
    "        res2 = []\n",
    "        for i in paths :\n",
    "            for item in i.split(\" \")[1:]:\n",
    "                tempd[i.split(\" \")[0] + \"/\" + item.split('(')[0]] = item.split('(')[1]\n",
    "        for k , v in tempd.items():\n",
    "            if v not in res.keys():\n",
    "                res[v]=[]\n",
    "            res[v].append(k)\n",
    "        for k1 , v1 in res.items():\n",
    "            if len(v1)>1:\n",
    "                res2.append(v1)\n",
    "        return res2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        tempd = {}\n",
    "        res = {}\n",
    "        res2 = []\n",
    "        for i in paths :\n",
    "            for item in i.split(\" \")[1:]:\n",
    "                tempd[i.split(\" \")[0] + \"/\" + item.split('(')[0]] = item.split('(')[1]\n",
    "        for k , v in tempd.items():\n",
    "            if v not in res.keys():\n",
    "                res[v]=[]\n",
    "            res[v].append(k)\n",
    "        for k1 , v1 in res.items():\n",
    "            if len(v1)>1:\n",
    "                res2.append(v1)\n",
    "        return res2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        tempi =[]\n",
    "        tempd = {}\n",
    "        res = {}\n",
    "        temp2=[]\n",
    "        res2 = []\n",
    "        for i in paths :\n",
    "            tempi = i.split(\" \")\n",
    "            for item in tempi[1:]:\n",
    "                tempd[tempi[0] + \"/\" + item.split('(')[0]] = item.split('(')[1].replace(\")\",\"\")\n",
    "        for k , v in tempd.items():\n",
    "            if v not in res.keys():\n",
    "                res[v]=[]\n",
    "            res[v].append(k)\n",
    "        for k1 , v1 in res.items():\n",
    "            \n",
    "            if len(v1)>1:\n",
    "                res2.append(v1)\n",
    "        return res2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        ans = []\n",
    "        resul = {}\n",
    "        len_p = len(paths)\n",
    "\n",
    "        for i in range(len_p):\n",
    "            # 截取文件内容和文件名称,用空格分割\n",
    "            dirf_files = paths[i].split(' ')\n",
    "            for k in range(1,len(dirf_files)):\n",
    "                # 分割每个文件内容\n",
    "                textname = dirf_files[k].split('.')\n",
    "                #放到字典\n",
    "                #resul[(dirf_files[0],textname[0])] = textname[1]\n",
    "                if textname[1] not in resul:\n",
    "                    resul[textname[1]] = [(dirf_files[0],textname[0])]\n",
    "                else:\n",
    "                    resul[textname[1]].append((dirf_files[0],textname[0]))\n",
    "\n",
    "        for _,item in enumerate(resul.items()):\n",
    "            tmpres = []\n",
    "            if len(item[1]) > 1:\n",
    "                for i in range(len(item[1])):\n",
    "                    tmpres.append(item[1][i][0]+'/'+item[1][i][1]+'.txt')\n",
    "                ans.append(tmpres)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import hashlib\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        d = {}\n",
    "        for path in paths:\n",
    "            p = path.split()\n",
    "            rp = p[0]\n",
    "            for i in range(1, len(p)):\n",
    "                c = self.getc(p[i])\n",
    "                fn = self.getfn(p[i])\n",
    "                md5c = self.md5(c)\n",
    "                if md5c not in d:\n",
    "                    d[md5c] = [rp+\"/\"+fn]\n",
    "                else:\n",
    "                    d[md5c].append(rp+\"/\"+fn)\n",
    "        r = []\n",
    "        for k in d:\n",
    "            v = d[k]\n",
    "            if len(v) > 1:\n",
    "                r.append(d[k])\n",
    "        return r\n",
    "\n",
    "\n",
    "    def md5(self, r:str) -> str:\n",
    "        hash_obj = hashlib.md5() \n",
    "        hash_obj.update(r.encode('utf-8'))\n",
    "        \n",
    "        return hash_obj.hexdigest()\n",
    "\n",
    "    def getfn(self, s:str) -> str:\n",
    "        r = \"\"\n",
    "\n",
    "        for ss in s:\n",
    "            if ss == '(':\n",
    "                return r\n",
    "            r += ss\n",
    "\n",
    "\n",
    "    def getc(self, s:str) -> str:\n",
    "        r = \"\"\n",
    "        f = 0\n",
    "\n",
    "        for ss in s:\n",
    "            if ss == ')':\n",
    "                return r\n",
    "            if f == 1:\n",
    "                r += ss\n",
    "            else:\n",
    "                if ss == '(':\n",
    "                    f = 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        arr_dict = defaultdict(list)\n",
    "        res_arr = []\n",
    "\n",
    "        for path in paths:\n",
    "            arr_path = path.split()\n",
    "            file_path = arr_path[0]\n",
    "            for file_index in range(1, len(arr_path)):\n",
    "                file_name, file_content = arr_path[file_index].split('(')\n",
    "                arr_dict[file_content].append((file_path, file_name))\n",
    "\n",
    "        for x in arr_dict.values():\n",
    "            res = []\n",
    "            if len(x) > 1:\n",
    "                for t in range(len(x)):\n",
    "                    full_name = x[t][0] + '/' + x[t][1]\n",
    "                    res.append(full_name)\n",
    "                res_arr.append(res)\n",
    "\n",
    "        return res_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = set()\n",
    "                \n",
    "                file_content_map[content].add(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = set()\n",
    "                \n",
    "                file_content_map[content].add(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        word = {}\n",
    "        for i in range(len(paths)):\n",
    "            sp = (paths[i].split(\" \"))\n",
    "            for fi in range(len(sp) - 1):\n",
    "                content = re.search(\"\\(\\w+\\)\", sp[fi + 1])\n",
    "                file = re.search(\"(.*?)\\.txt\", sp[fi + 1])\n",
    "                contentw = content.group()\n",
    "                filew = sp[0] + \"/\" + file.group()\n",
    "                if word.get(contentw) == None:\n",
    "                    word[contentw] = set()\n",
    "                    word[contentw].add(filew)\n",
    "                else:\n",
    "                    word[contentw].add(filew)\n",
    "\n",
    "        ans = []\n",
    "        for k, v in word.items():\n",
    "            if len(v) >= 2:\n",
    "                ans.append(list(v))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDuplicate(self, paths: List[str]) -> List[List[str]]:\n",
    "        res = []\n",
    "        file_content_map = {}\n",
    "\n",
    "        for path in paths:\n",
    "            tokens = path.split()\n",
    "            directory = tokens[0]\n",
    "            \n",
    "            for i in range(1, len(tokens)):\n",
    "                idx = tokens[i].index(\"(\")\n",
    "                content = tokens[i][idx:]\n",
    "                file_path = directory + \"/\" + tokens[i][:idx]\n",
    "                \n",
    "                if content not in file_content_map:\n",
    "                    file_content_map[content] = set()\n",
    "                \n",
    "                file_content_map[content].add(file_path)\n",
    "\n",
    "        for key in file_content_map:\n",
    "            if len(file_content_map[key]) > 1:\n",
    "                res.append(list(file_content_map[key]))\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
